/*
** Procedures for generating reports and tables in the LEMON parser generator.
*/
#include <algorithm>
#include <map>
#include "config.h"
#include "struct.h"
#include "symbol.h"
#include "set.h"
#include "action.h"
#include "error.h"
#include "configlist.h"
#include "lemon.h"

/* Generate a filename with the given suffix.  Space to hold the
** name comes from malloc() and must be freed by the calling
** function.
*/
PRIVATE char *file_makename(Lemon *lemp, const char *suffix)
{
  char *name;
  char *cp;

  name = (char*)malloc( lemonStrlen(lemp->filename) + lemonStrlen(suffix) + 5 );
  if (name==0) {
    fprintf(stderr,"Can't allocate space for a filename.\n");
    exit(1);
  }
  strcpy(name,lemp->filename);
  cp = strrchr(name,'.');
  if (cp ) *cp = 0;
  strcat(name,suffix);
  return name;
}

/* Open a file with a name based on the name of the input file,
** but with a different (specified) suffix, and return a pointer
** to the stream */
PRIVATE FILE *file_open(
  Lemon *lemp,
  const char *suffix,
  const char *mode
){
  FILE *fp;

  if (lemp->outname) free(lemp->outname);
  lemp->outname = file_makename(lemp, suffix);
  fp = fopen(lemp->outname,mode);
  if (fp==0 && *mode=='w') {
    fprintf(stderr,"Can't open file \"%s\".\n",lemp->outname);
    lemp->errorcnt++;
    return 0;
  }
  return fp;
}

/* Duplicate the input file without comments and without actions 
** on rules */
void Reprint(Lemon *lemp)
{
  Symbol *sp;
  int i, j, maxlen, len, ncolumns, skip;
  printf("// Reprint of input file \"%s\".\n// Symbols:\n",lemp->filename);
  maxlen = 10;
  for (i=0; i<lemp->nsymbol; i++) {
    sp = lemp->symbols[i];
    len = lemonStrlen(sp->name);
    if (len>maxlen) maxlen = len;
  }
  ncolumns = 76/(maxlen+5);
  if (ncolumns<1) ncolumns = 1;
  skip = (lemp->nsymbol + ncolumns - 1)/ncolumns;
  for (i=0; i<skip; i++) {
    printf("//");
    for (j=i; j<lemp->nsymbol; j+=skip) {
      sp = lemp->symbols[j];
      assert( sp->index==j);
      printf(" %3d %-*.*s",j,maxlen,maxlen,sp->name);
    }
    printf("\n");
  }
  for (Rule* rp : lemp->rules) {
    printf("%s",rp->lhs->name);
    /*    if( rp->lhsalias ) printf("(%s)",rp->lhsalias); */
    printf(" ::=");
    for (Symbol* sym : rp->rhs) {
      if (sym->type == MULTITERMINAL) {
        printf(" %s", sym->subsyms[0]->name);
        for (auto it = ++sym->subsyms.begin(); it != sym->subsyms.end(); ++it) {
          printf("|%s", (*it)->name);
        }
      } else {
        printf(" %s", sym->name);
      }
      /* if( rp->rhsalias[i] ) printf("(%s)",rp->rhsalias[i]); */
    }
    printf(".");
    if (rp->precsym) printf(" [%s]",rp->precsym->name);
    /* if( rp->code ) printf("\n    %s",rp->code); */
    printf("\n");
  }
}

/* Print a single rule.
*/
void RulePrint(FILE *fp, Rule *rp, int iCursor){
  Symbol *sp;
  fprintf(fp,"%s ::=",rp->lhs->name);
  for (int i=0; i<=rp->rhs.size(); i++) {
    if (i==iCursor) fprintf(fp," *");
    if (i==rp->rhs.size()) break;
    sp = rp->rhs[i];
    if (sp->type==MULTITERMINAL) {
      fprintf(fp," %s", sp->subsyms[0]->name);
      for (auto it = ++sp->subsyms.begin(); it != sp->subsyms.end(); ++it) {
        fprintf(fp,"|%s", (*it)->name);
      }
    } else {
      fprintf(fp," %s", sp->name);
    }
  }
}

/* convenient gdb calls */
#if !defined(NDEBUG)
void prule(Rule* rule)
{
  RulePrint(stdout, rule, 0);
  printf("\n");
  fflush(stdout);
}
void pconfig(Config* conf)
{
  RulePrint(stdout, conf->rp, conf->dot);
  printf("\n");
  fflush(stdout);
}
#endif

/* Print the rule for a configuration.
*/
void ConfigPrint(FILE *fp, Config *cfp) {
  RulePrint(fp, cfp->rp, cfp->dot);
}

//#define LEMON_TEST
#if defined(LEMON_TEST)
/* Print a set */
PRIVATE void SetPrint(FILE* out, char* set, Lemon* lemp)
{
  int i;
  const char *spacer = "";
  fprintf(out,"%12s[","");
  for (i=0; i<lemp->nterminal; i++) {
    if (SetFind(set,i)) {
      fprintf(out,"%s%s",spacer,lemp->symbols[i]->name);
      spacer = " ";
    }
  }
  fprintf(out,"]\n");
}

/* Print a plink chain */
PRIVATE void PlinkPrint(FILE* out, ConfigList& plp, const char* tag)
{
  for (Config* conf : plp) {
    fprintf(out, "%12s%s (state %2d) ", "", tag, conf->stp->statenum);
    ConfigPrint(out, conf);
    fprintf(out, "\n");
  }
}
#endif // LEMON_TEST

extern int showPrecedenceConflict;
/* Print an action to the given file descriptor.  Return FALSE if
** nothing was actually printed.
*/
int PrintAction(
  Action *ap,          /* The action to print */
  FILE *fp,                   /* Print the action here */
  int indent                  /* Indent by this amount */
){
  int result = 1;
  switch( ap->type) {
    case SHIFT: {
      State *stp = ap->x.stp;
      fprintf(fp,"%*s shift        %-7d",indent,ap->sp->name,stp->statenum);
      break;
    }
    case REDUCE: {
      Rule *rp = ap->x.rp;
      fprintf(fp,"%*s reduce       %-7d",indent,ap->sp->name,rp->iRule);
      RulePrint(fp, rp, -1);
      break;
    }
    case SHIFTREDUCE: {
      Rule *rp = ap->x.rp;
      fprintf(fp,"%*s shift-reduce %-7d",indent,ap->sp->name,rp->iRule);
      RulePrint(fp, rp, -1);
      break;
    }
    case ACCEPT:
      fprintf(fp,"%*s accept",indent,ap->sp->name);
      break;
    case ERROR:
      fprintf(fp,"%*s error",indent,ap->sp->name);
      break;
    case SRCONFLICT:
    case RRCONFLICT:
      fprintf(fp,"%*s reduce       %-7d ** Parsing conflict **",
        indent,ap->sp->name,ap->x.rp->iRule);
      break;
    case SSCONFLICT:
      fprintf(fp,"%*s shift        %-7d ** Parsing conflict **", 
        indent,ap->sp->name,ap->x.stp->statenum);
      break;
    case SH_RESOLVED:
      if (showPrecedenceConflict) {
        fprintf(fp,"%*s shift        %-7d -- dropped by precedence",
                indent,ap->sp->name,ap->x.stp->statenum);
      } else {
        result = 0;
      }
      break;
    case RD_RESOLVED:
      if (showPrecedenceConflict) {
        fprintf(fp,"%*s reduce %-7d -- dropped by precedence",
                indent,ap->sp->name,ap->x.rp->iRule);
      } else {
        result = 0;
      }
      break;
    case NOT_USED:
      result = 0;
      break;
  }
  return result;
}

/* Generate the "*.out" log file */
void ReportOutput(Lemon *lemp)
{
  FILE* fp = file_open(lemp,".out","wb");
  if (fp==0) return;

  for (int i=0; i < lemp->nxstate; i++) {
    State* state = lemp->sorted_states[i];
    fprintf(fp,"State %d:\n",state->statenum);
    ConfigList& cf_list = lemp->basisflag ? state->basis_configs : state->configs;
    for (Config* config : cf_list) {
      char buf[20];
      if (config->dot == config->rp->rhs.size()) {
        sprintf(buf,"(%d)",config->rp->iRule);
        fprintf(fp,"    %5s ",buf);
      } else {
        fprintf(fp,"          ");
      }
      ConfigPrint(fp,config);
      fprintf(fp,"\n");
#if defined(LEMON_TEST)
      SetPrint(fp,config->fws,lemp);
      PlinkPrint(fp, config->fplp, "To  ");
      PlinkPrint(fp, config->bplp, "From");
#endif
    }
    fprintf(fp,"\n");
    for (Action* action : state->actions) {
      if (PrintAction(action, fp, 30)) fprintf(fp,"\n");
    }
    fprintf(fp,"\n");
  }
  fprintf(fp, "----------------------------------------------------\n");
  fprintf(fp, "Symbols:\n");
  for (int i=0; i < lemp->nsymbol; i++) {
    Symbol *sym = lemp->symbols[i];
    fprintf(fp, "  %3d: %s", i, sym->name);
    if (sym->type==NONTERMINAL) {
      fprintf(fp, ":");
      if (sym->lambda) {
        fprintf(fp, " <lambda>");
      }
      for (int j=0; j<lemp->nterminal; j++) {
        if (sym->firstset && SetFind(sym->firstset, j)) {
          fprintf(fp, " %s", lemp->symbols[j]->name);
        }
      }
    }
    fprintf(fp, "\n");
  }
  fclose(fp);
  return;
}

/* Search for the file "name" which is in the same directory as
** the executable */
PRIVATE char *pathsearch(char *argv0, char *name, int modemask)
{
  const char *pathlist;
  char *pathbufptr;
  char *pathbuf;
  char *path,*cp;
  char c;

#ifdef __WIN32__
  cp = strrchr(argv0,'\\');
#else
  cp = strrchr(argv0,'/');
#endif
  if (cp) {
    c = *cp;
    *cp = 0;
    path = (char *)malloc( lemonStrlen(argv0) + lemonStrlen(name) + 2);
    if (path) sprintf(path,"%s/%s",argv0,name);
    *cp = c;
  } else {
    pathlist = getenv("PATH");
    if (pathlist==0) pathlist = ".:/bin:/usr/bin";
    pathbuf = (char *) malloc( lemonStrlen(pathlist) + 1 );
    path = (char *)malloc( lemonStrlen(pathlist)+lemonStrlen(name)+2 );
    if ((pathbuf != 0) && (path!=0)) {
      pathbufptr = pathbuf;
      strcpy(pathbuf, pathlist);
      while (*pathbuf) {
        cp = strchr(pathbuf,':');
        if (cp==0) cp = &pathbuf[lemonStrlen(pathbuf)];
        c = *cp;
        *cp = 0;
        sprintf(path,"%s/%s",pathbuf,name);
        *cp = c;
        if (c==0) pathbuf[0] = 0;
        else pathbuf = &cp[1];
        if (access(path,modemask)==0) break;
      }
      free(pathbufptr);
    }
  }
  return path;
}

/* Given an action, compute the integer value for that action
** which is to be put in the action table of the generated machine.
** Return negative if no action should be generated.
*/
PRIVATE int compute_action(Lemon *lemp, Action *ap)
{
  int act;
  int nstate = lemp->sorted_states.size();
  switch (ap->type) {
  case SHIFT:  act = ap->x.stp->statenum;                  break;
  case SHIFTREDUCE: act = ap->x.rp->iRule + nstate;        break;
  case REDUCE: act = ap->x.rp->iRule + nstate+lemp->nrule; break;
  case ERROR:  act = nstate + lemp->nrule*2;               break;
  case ACCEPT: act = nstate + lemp->nrule*2 + 1;           break;
  default:     act = -1; break;
  }
  return act;
}

#define LINESIZE 1000
/* The next cluster of routines are for reading the template file
** and writing the results to the generated parser */
/* The first function transfers data from "in" to "out" until
** a line is seen which begins with "%%".  The line number is
** tracked.
**
** if name!=0, then any word that begin with "Parse" is changed to
** begin with *name instead.
*/
PRIVATE void tplt_xfer(char *name, FILE *in, FILE *out, int *lineno)
{
  int i, iStart;
  char line[LINESIZE];
  while (fgets(line,LINESIZE,in) && (line[0]!='%' || line[1]!='%')) {
    (*lineno)++;
    iStart = 0;
    if (name) {
      for (i=0; line[i]; i++) {
        if (line[i]=='P' && strncmp(&line[i],"Parse",5)==0
          && (i==0 || !ISALPHA(line[i-1]))
       ) {
          if (i>iStart) fprintf(out,"%.*s",i-iStart,&line[iStart]);
          fprintf(out,"%s",name);
          i += 4;
          iStart = i+1;
        }
      }
    }
    fprintf(out,"%s",&line[iStart]);
  }
}
extern char *user_templatename;
/* The next function finds the template file and opens it, returning
** a pointer to the opened file. */
PRIVATE FILE *tplt_open(Lemon *lemp)
{
  static char templatename[] = "lempar.c";
  char buf[1000];
  FILE *in;
  char *tpltname;
  char *cp;

  /* first, see if user specified a template filename on the command line. */
  if (user_templatename != 0) {
    if (access(user_templatename,004)==-1) {
      fprintf(stderr,"Can't find the parser driver template file \"%s\".\n",
        user_templatename);
      lemp->errorcnt++;
      return 0;
    }
    in = fopen(user_templatename,"rb");
    if (in==0) {
      fprintf(stderr,"Can't open the template file \"%s\".\n",
              user_templatename);
      lemp->errorcnt++;
      return 0;
    }
    return in;
  }

  cp = strrchr(lemp->filename,'.');
  if (cp) {
    sprintf(buf,"%.*s.lt",(int)(cp-lemp->filename),lemp->filename);
  } else {
    sprintf(buf,"%s.lt",lemp->filename);
  }
  if (access(buf,004)==0) {
    tpltname = buf;
  } else if (access(templatename,004)==0) {
    tpltname = templatename;
  } else {
    tpltname = pathsearch(lemp->argv0,templatename,0);
  }
  if (tpltname==0) {
    fprintf(stderr,"Can't find the parser driver template file \"%s\".\n",
    templatename);
    lemp->errorcnt++;
    return 0;
  }
  in = fopen(tpltname,"rb");
  if (in==0) {
    fprintf(stderr,"Can't open the template file \"%s\".\n",templatename);
    lemp->errorcnt++;
    return 0;
  }
  return in;
}

/* Print a #line directive line to the output file. */
PRIVATE void tplt_linedir(FILE *out, int lineno, char *filename)
{
  fprintf(out,"#line %d \"",lineno);
  while (*filename) {
    if (*filename == '\\') putc('\\',out);
    putc(*filename,out);
    filename++;
  }
  fprintf(out,"\"\n");
}

/* Print a string to the file and keep the linenumber up to date */
PRIVATE void tplt_print(FILE *out, Lemon *lemp, char *str, int *lineno)
{
  if (str==0) return;
  while (*str) {
    putc(*str,out);
    if (*str=='\n') (*lineno)++;
    str++;
  }
  if (str[-1]!='\n') {
    putc('\n',out);
    (*lineno)++;
  }
  if (!lemp->nolinenosflag) {
    (*lineno)++; tplt_linedir(out,*lineno,lemp->outname); 
  }
  return;
}

/*
** The following routine emits code for the destructor for the
** symbol sp
*/
void emit_destructor_code(
  FILE *out,
  Symbol *sp,
  Lemon *lemp,
  int *lineno
){
 char *cp = 0;

 if (sp->type==TERMINAL) {
   cp = lemp->tokendest;
   if (cp==0) return;
   fprintf(out,"{\n"); (*lineno)++;
 } else if (sp->destructor) {
   cp = sp->destructor;
   fprintf(out,"{\n"); (*lineno)++;
   if (!lemp->nolinenosflag) {
     (*lineno)++;
     tplt_linedir(out,sp->destLineno,lemp->filename);
   }
 } else if (lemp->vardest) {
   cp = lemp->vardest;
   if (cp==0) return;
   fprintf(out,"{\n"); (*lineno)++;
 } else {
   assert( 0 );  /* Cannot happen */
 }
 for (; *cp; cp++) {
   if (*cp=='$' && cp[1]=='$') {
     fprintf(out,"(yypminor->yy%d)",sp->dtnum);
     cp++;
     continue;
   }
   if (*cp=='\n') (*lineno)++;
   fputc(*cp,out);
 }
 fprintf(out,"\n"); (*lineno)++;
 if (!lemp->nolinenosflag) { 
   (*lineno)++; tplt_linedir(out,*lineno,lemp->outname); 
 }
 fprintf(out,"}\n"); (*lineno)++;
 return;
}

/*
** Return TRUE (non-zero) if the given symbol has a destructor.
*/
int has_destructor(Symbol *sp, Lemon *lemp)
{
  int ret;
  if (sp->type==TERMINAL) {
    ret = lemp->tokendest!=0;
  } else {
    ret = lemp->vardest!=0 || sp->destructor!=0;
  }
  return ret;
}

/*
** Append text to a dynamically allocated string.  If zText is 0 then
** reset the string to be empty again.  Always return the complete text
** of the string (which is overwritten with each call).
**
** n bytes of zText are stored.  If n==0 then all of zText up to the first
** \000 terminator is stored.  zText can contain up to two instances of
** %d.  The values of p1 and p2 are written into the first and second
** %d.
**
** If n==-1, then the previous character is overwritten.
*/
PRIVATE char *append_str(const char *zText, int n, int p1, int p2){
  static char empty[1] = { 0 };
  static char *z = 0;
  static int alloced = 0;
  static int used = 0;
  int c;
  char zInt[40];
  if (zText==0) {
    if (used==0 && z!=0) z[0] = 0;
    used = 0;
    return z;
  }
  if (n<=0) {
    if (n<0) {
      used += n;
      assert( used>=0 );
    }
    n = lemonStrlen(zText);
  }
  if ((int) (n+sizeof(zInt)*2+used) >= alloced) {
    alloced = n + sizeof(zInt)*2 + used + 200;
    z = (char *) realloc(z,  alloced);
  }
  if (z==0) return empty;
  while (n-- > 0) {
    c = *(zText++);
    if (c=='%' && n>0 && zText[0]=='d') {
      sprintf(zInt, "%d", p1);
      p1 = p2;
      strcpy(&z[used], zInt);
      used += lemonStrlen(&z[used]);
      zText++;
      n--;
    } else {
      z[used++] = (char)c;
    }
  }
  z[used] = 0;
  return z;
}

/*
** zCode is a string that is the action associated with a rule.  Expand
** the symbols in this string so that they refer to elements of the parser
** stack.
**
** Return 1 if the expanded code requires that "yylhsminor" local variable
** to be defined.
*/
PRIVATE int translate_code(Lemon *lemp, Rule *rp){
  char *cp, *xp;
  int i;
  int rc = 0;            /* True if yylhsminor is used */
  int dontUseRhs0 = 0;   /* If true, use of left-most RHS label is illegal */
  const char *zSkip = 0; /* The zOvwrt comment within rp->code, or NULL */
  char lhsused = 0;      /* True if the LHS element has been used */
  char lhsdirect;        /* True if LHS writes directly into stack */
  char used[MAXRHS];     /* True for each RHS element which is used */
  char zLhs[50];         /* Convert the LHS symbol into this string */
  char zOvwrt[900];      /* Comment that to allow LHS to overwrite RHS */

  for (i=0; i<rp->rhs.size(); i++) used[i] = 0;
  lhsused = 0;

  if (rp->code==0) {
    static char newlinestr[2] = { '\n', '\0' };
    rp->code = newlinestr;
    rp->line = rp->ruleline;
  }


  if (rp->rhs.empty()) {
    /* If there are no RHS symbols, then writing directly to the LHS is ok */
    lhsdirect = 1;
  } else if (rp->rhsalias[0]==0) {
    /* The left-most RHS symbol has no value.  LHS direct is ok.  But
    ** we have to call the destructor on the RHS symbol first. */
    lhsdirect = 1;
    if (has_destructor(rp->rhs[0],lemp)) {
      append_str(0,0,0,0);
      append_str("  yy_destructor(yypParser,%d,&yymsp[%d].minor);\n", 0,
                 rp->rhs[0]->index, 1 - rp->rhs.size());
      rp->codePrefix = Strsafe(append_str(0,0,0,0));
    }
  } else if (rp->lhsalias==0) {
    /* There is no LHS value symbol. */
    lhsdirect = 1;
  } else if (strcmp(rp->lhsalias,rp->rhsalias[0])==0) {
    /* The LHS symbol and the left-most RHS symbol are the same, so 
    ** direct writing is allowed */
    lhsdirect = 1;
    lhsused = 1;
    used[0] = 1;
    if (rp->lhs->dtnum!=rp->rhs[0]->dtnum) {
      ErrorMsg(lemp->filename,rp->ruleline,
        "%s(%s) and %s(%s) share the same label but have "
        "different datatypes.",
        rp->lhs->name, rp->lhsalias, rp->rhs[0]->name, rp->rhsalias[0]);
      lemp->errorcnt++;
    }    
  } else {
    sprintf(zOvwrt, "/*%s-overwrites-%s*/",
                  rp->lhsalias, rp->rhsalias[0]);
    zSkip = strstr(rp->code, zOvwrt);
    if (zSkip!=0) {
      /* The code contains a special comment that indicates that it is safe
      ** for the LHS label to overwrite left-most RHS label. */
      lhsdirect = 1;
    } else {
      lhsdirect = 0;
    }
  }
  if (lhsdirect) {
    sprintf(zLhs, "yymsp[%d].minor.yy%d", 1 - (int)rp->rhs.size(), rp->lhs->dtnum);
  } else {
    rc = 1;
    sprintf(zLhs, "yylhsminor.yy%d",rp->lhs->dtnum);
  }

  append_str(0,0,0,0);

  /* This const cast is wrong but harmless, if we're careful. */
  for (cp=(char *)rp->code; *cp; cp++) {
    if (cp==zSkip) {
      append_str(zOvwrt,0,0,0);
      cp += lemonStrlen(zOvwrt)-1;
      dontUseRhs0 = 1;
      continue;
    }
    if (ISALPHA(*cp) && (cp==rp->code || (!ISALNUM(cp[-1]) && cp[-1]!='_'))) {
      char saved;
      for (xp= &cp[1]; ISALNUM(*xp) || *xp=='_'; xp++);
      saved = *xp;
      *xp = 0;
      if (rp->lhsalias && strcmp(cp,rp->lhsalias)==0) {
        append_str(zLhs,0,0,0);
        cp = xp;
        lhsused = 1;
      } else {
        for (i=0; i<rp->rhs.size(); i++) {
          if (rp->rhsalias[i] && strcmp(cp,rp->rhsalias[i])==0) {
            if (i==0 && dontUseRhs0) {
              ErrorMsg(lemp->filename,rp->ruleline,
                 "Label %s used after '%s'.",
                 rp->rhsalias[0], zOvwrt);
              lemp->errorcnt++;
            } else if (cp!=rp->code && cp[-1]=='@') {
              /* If the argument is of the form @X then substituted
              ** the token number of X, not the value of X */
              append_str("yymsp[%d].major",-1, i-(int)rp->rhs.size()+1, 0);
            } else {
              Symbol *sp = rp->rhs[i];
              int dtnum;
              if (sp->type==MULTITERMINAL) {
                dtnum = sp->subsyms[0]->dtnum;
              } else {
                dtnum = sp->dtnum;
              }
              append_str("yymsp[%d].minor.yy%d", 0, i-rp->rhs.size()+1, dtnum);
            }
            cp = xp;
            used[i] = 1;
            break;
          }
        }
      }
      *xp = saved;
    }
    append_str(cp, 1, 0, 0);
  } /* End loop */

  /* Main code generation completed */
  cp = append_str(0,0,0,0);
  if (cp && cp[0]) rp->code = Strsafe(cp);
  append_str(0,0,0,0);

  /* Check to make sure the LHS has been used */
  if (rp->lhsalias && !lhsused) {
    ErrorMsg(lemp->filename,rp->ruleline,
      "Label \"%s\" for \"%s(%s)\" is never used.",
        rp->lhsalias,rp->lhs->name,rp->lhsalias);
    lemp->errorcnt++;
  }

  /* Generate destructor code for RHS minor values which are not referenced.
  ** Generate error messages for unused labels and duplicate labels.
  */
  for (i=0; i < rp->rhs.size(); i++) {
    if (rp->rhsalias[i]) {
      if (i>0) {
        int j;
        if (rp->lhsalias && strcmp(rp->lhsalias,rp->rhsalias[i])==0) {
          ErrorMsg(lemp->filename,rp->ruleline,
            "%s(%s) has the same label as the LHS but is not the left-most "
            "symbol on the RHS.",
            rp->rhs[i]->name, rp->rhsalias[0]);
          lemp->errorcnt++;
        }
        for (j=0; j<i; j++) {
          if (rp->rhsalias[j] && strcmp(rp->rhsalias[j],rp->rhsalias[i])==0) {
            ErrorMsg(lemp->filename,rp->ruleline,
              "Label %s used for multiple symbols on the RHS of a rule.",
              rp->rhsalias[i]);
            lemp->errorcnt++;
            break;
          }
        }
      }
      if (!used[i]) {
        ErrorMsg(lemp->filename,rp->ruleline,
          "Label %s for \"%s(%s)\" is never used.",
          rp->rhsalias[i],rp->rhs[i]->name,rp->rhsalias[i]);
        lemp->errorcnt++;
      }
    } else if (i>0 && has_destructor(rp->rhs[i],lemp)) {
      append_str("  yy_destructor(yypParser,%d,&yymsp[%d].minor);\n", 0,
                 rp->rhs[i]->index, i-(int)rp->rhs.size()+1);
    }
  }

  /* If unable to write LHS values directly into the stack, write the
  ** saved LHS value now. */
  if (lhsdirect==0) {
    append_str("  yymsp[%d].minor.yy%d = ", 0, 1-rp->rhs.size(), rp->lhs->dtnum);
    append_str(zLhs, 0, 0, 0);
    append_str(";\n", 0, 0, 0);
  }

  /* Suffix code generation complete */
  cp = append_str(0,0,0,0);
  if (cp && cp[0]) rp->codeSuffix = Strsafe(cp);

  return rc;
}

/* 
** Generate code which executes when the rule "rp" is reduced.  Write
** the code to "out".  Make sure lineno stays up-to-date.
*/
PRIVATE void emit_code(
  FILE *out,
  Rule *rp,
  Lemon *lemp,
  int *lineno
){
 const char *cp;

 /* Setup code prior to the #line directive */
 if (rp->codePrefix && rp->codePrefix[0]) {
   fprintf(out, "{%s", rp->codePrefix);
   for (cp=rp->codePrefix; *cp; cp++) { if (*cp=='\n') (*lineno)++; }
 }

 /* Generate code to do the reduce action */
 if (rp->code) {
   if (!lemp->nolinenosflag) {
     (*lineno)++;
     tplt_linedir(out,rp->line,lemp->filename);
   }
   fprintf(out,"{%s",rp->code);
   for (cp=rp->code; *cp; cp++) { if (*cp=='\n') (*lineno)++; }
   fprintf(out,"}\n"); (*lineno)++;
   if (!lemp->nolinenosflag) {
     (*lineno)++;
     tplt_linedir(out,*lineno,lemp->outname);
   }
 }

 /* Generate breakdown code that occurs after the #line directive */
 if (rp->codeSuffix && rp->codeSuffix[0]) {
   fprintf(out, "%s", rp->codeSuffix);
   for (cp=rp->codeSuffix; *cp; cp++) { if (*cp=='\n') (*lineno)++; }
 }

 if (rp->codePrefix) {
   fprintf(out, "}\n"); (*lineno)++;
 }

 return;
}

/*
** Print the definition of the union used for the parser's data stack.
** This union contains fields for every possible data type for tokens
** and nonterminals.  In the process of computing and printing this
** union, also set the ".dtnum" field of every terminal and nonterminal
** symbol.
*/
void print_stack_union(
  FILE *out,                  /* The output stream */
  Lemon *lemp,         /* The main info structure for this parser */
  int *plineno,               /* Pointer to the line number */
  int mhflag                  /* True if generating makeheaders output */
){
  int lineno = *plineno;    /* The line number of the output */
  char **types;             /* A hash table of datatypes */
  int arraysize;            /* Size of the "types" array */
  int maxdtlength;          /* Maximum length of any ".datatype" field. */
  char *stddt;              /* Standardized name for a datatype */
  int i,j;                  /* Loop counters */
  unsigned hash;            /* For hashing the name of a type */
  const char *name;         /* Name of the parser */

  /* Allocate and initialize types[] and allocate stddt[] */
  arraysize = lemp->nsymbol * 2;
  types = (char**)calloc( arraysize, sizeof(char*) );
  if (types==0) {
    fprintf(stderr,"Out of memory.\n");
    exit(1);
  }
  for (i=0; i<arraysize; i++) types[i] = 0;
  maxdtlength = 0;
  if (lemp->vartype) {
    maxdtlength = lemonStrlen(lemp->vartype);
  }
  for (i=0; i<lemp->nsymbol; i++) {
    int len;
    Symbol *sp = lemp->symbols[i];
    if (sp->datatype==0) continue;
    len = lemonStrlen(sp->datatype);
    if (len>maxdtlength) maxdtlength = len;
  }
  stddt = (char*)malloc( maxdtlength*2 + 1 );
  if (stddt==0) {
    fprintf(stderr,"Out of memory.\n");
    exit(1);
  }

  /* Build a hash table of datatypes. The ".dtnum" field of each symbol
  ** is filled in with the hash index plus 1.  A ".dtnum" value of 0 is
  ** used for terminal symbols.  If there is no %default_type defined then
  ** 0 is also used as the .dtnum value for nonterminals which do not specify
  ** a datatype using the %type directive.
  */
  for (i=0; i<lemp->nsymbol; i++) {
    Symbol *sp = lemp->symbols[i];
    char *cp;
    if (sp==lemp->errsym) {
      sp->dtnum = arraysize+1;
      continue;
    }
    if (sp->type!=NONTERMINAL || (sp->datatype==0 && lemp->vartype==0)) {
      sp->dtnum = 0;
      continue;
    }
    cp = sp->datatype;
    if (cp==0) cp = lemp->vartype;
    j = 0;
    while( ISSPACE(*cp) ) cp++;
    while( *cp ) stddt[j++] = *cp++;
    while( j>0 && ISSPACE(stddt[j-1]) ) j--;
    stddt[j] = 0;
    if (lemp->tokentype && strcmp(stddt, lemp->tokentype)==0) {
      sp->dtnum = 0;
      continue;
    }
    hash = 0;
    for (j=0; stddt[j]; j++) {
      hash = hash*53 + stddt[j];
    }
    hash = (hash & 0x7fffffff)%arraysize;
    while (types[hash]) {
      if (strcmp(types[hash],stddt)==0) {
        sp->dtnum = hash + 1;
        break;
      }
      hash++;
      if (hash>=(unsigned)arraysize) hash = 0;
    }
    if (types[hash]==0) {
      sp->dtnum = hash + 1;
      types[hash] = (char*)malloc( lemonStrlen(stddt)+1 );
      if (types[hash]==0) {
        fprintf(stderr,"Out of memory.\n");
        exit(1);
      }
      strcpy(types[hash],stddt);
    }
  }

  /* Print out the definition of YYTOKENTYPE and YYMINORTYPE */
  name = lemp->name ? lemp->name : "Parse";
  lineno = *plineno;
  if (mhflag) { fprintf(out,"#if INTERFACE\n"); lineno++; }
  fprintf(out,"#define %sTOKENTYPE %s\n",name,
    lemp->tokentype?lemp->tokentype:"void*");  lineno++;
  if (mhflag) { fprintf(out,"#endif\n"); lineno++; }
  fprintf(out,"typedef union {\n"); lineno++;
  fprintf(out,"  int yyinit;\n"); lineno++;
  fprintf(out,"  %sTOKENTYPE yy0;\n",name); lineno++;
  for (i=0; i<arraysize; i++) {
    if (types[i]==0) continue;
    fprintf(out,"  %s yy%d;\n",types[i],i+1); lineno++;
    free(types[i]);
  }
  if (lemp->errsym->useCnt) {
    fprintf(out,"  int yy%d;\n",lemp->errsym->dtnum); lineno++;
  }
  free(stddt);
  free(types);
  fprintf(out,"} YYMINORTYPE;\n"); lineno++;
  *plineno = lineno;
}

/*
** Return the name of a C datatype able to represent values between
** lwr and upr, inclusive.  If pnByte!=NULL then also write the sizeof
** for that type (1, 2, or 4) into *pnByte.
*/
static const char *minimum_size_type(int lwr, int upr, int *pnByte){
  const char *zType = "int";
  int nByte = 4;
  if (lwr>=0) {
    if (upr<=255) {
      zType = "unsigned char";
      nByte = 1;
    } else if (upr<65535) {
      zType = "unsigned short int";
      nByte = 2;
    } else {
      zType = "unsigned int";
      nByte = 4;
    }
  } else if (lwr>=-127 && upr<=127) {
    zType = "signed char";
    nByte = 1;
  } else if (lwr>=-32767 && upr<32767) {
    zType = "short";
    nByte = 2;
  }
  if (pnByte) *pnByte = nByte;
  return zType;
}

/*
** Each state contains a set of token transaction and a set of
** nonterminal transactions.  Each of these sets makes an instance
** of the following structure.  An array of these structures is used
** to order the creation of entries in the yy_action[] table.
*/
struct axset {
  State *stp;   /* A pointer to a state */
  int isTkn;           /* True to use tokens.  False for non-terminals */
  int nAction;         /* Number of actions */
  int iOrder;          /* Original order of action sets */
  axset():stp(0),isTkn(0),nAction(0),iOrder(0){}
  bool operator == (const axset& o) const {
    return stp==o.stp && isTkn==o.isTkn && nAction==o.nAction && iOrder==o.iOrder;}
};

/*
** Compare to axset structures for sorting purposes
*/
static int axset_compare(const axset& a, const axset& b){
  int c;
  c = b.nAction - a.nAction;
  if (c==0) {
    c = a.iOrder - b.iOrder;
  }
  assert( c!=0 || a==b );
  return c;
}

/*
** Write text on "out" that describes the rule "rp".
*/
static void writeRuleText(FILE *out, Rule *rp){
  fprintf(out,"%s ::=", rp->lhs->name);
  for (Symbol* sp : rp->rhs) {
    if (sp->type != MULTITERMINAL) {
      fprintf(out," %s", sp->name);
    } else {
      fprintf(out," %s", sp->subsyms[0]->name);
      for (auto it = ++sp->subsyms.begin(); it != sp->subsyms.end(); ++it) {
        fprintf(out,"|%s", (*it)->name);
      }
    }
  }
}


/* Generate C source code for the parser */
void ReportTable(
  Lemon *lemp,
  int mhflag     /* Output in makeheaders format if true */
){
  FILE* in = tplt_open(lemp);
  if (in==0) return;
  FILE* out = file_open(lemp,".c","wb");
  if (out==0) {
    fclose(in);
    return;
  }
  int lineno = 1;
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate the include code, if any */
  tplt_print(out,lemp,lemp->include,&lineno);
  if (mhflag) {
    char *incName = file_makename(lemp, ".h");
    fprintf(out,"#include \"%s\"\n", incName); lineno++;
    free(incName);
  }
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate #defines for all tokens */
  if (mhflag) {
    const char *prefix;
    fprintf(out,"#if INTERFACE\n"); lineno++;
    if (lemp->tokenprefix) prefix = lemp->tokenprefix;
    else                    prefix = "";
    for (int i=1; i<lemp->nterminal; i++) {
      fprintf(out,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);
      lineno++;
    }
    fprintf(out,"#endif\n"); lineno++;
  }
  tplt_xfer(lemp->name,in,out,&lineno);

  int nstate = lemp->sorted_states.size();
  int szActionType;     /* sizeof(YYACTIONTYPE) */
  int szCodeType;       /* sizeof(YYCODETYPE)   */

  /* Generate the defines */
  fprintf(out,"#define YYCODETYPE %s\n",
    minimum_size_type(0, lemp->nsymbol+1, &szCodeType)); lineno++;
  fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1);  lineno++;
  fprintf(out,"#define YYACTIONTYPE %s\n",
    minimum_size_type(0,nstate+lemp->nrule*2+5,&szActionType)); lineno++;
  if (lemp->wildcard) {
    fprintf(out,"#define YYWILDCARD %d\n",
       lemp->wildcard->index); lineno++;
  }
  print_stack_union(out,lemp,&lineno,mhflag);
  fprintf(out, "#ifndef YYSTACKDEPTH\n"); lineno++;
  if (lemp->stacksize) {
    fprintf(out,"#define YYSTACKDEPTH %s\n",lemp->stacksize);  lineno++;
  } else {
    fprintf(out,"#define YYSTACKDEPTH 100\n");  lineno++;
  }
  fprintf(out, "#endif\n"); lineno++;
  if (mhflag) {
    fprintf(out,"#if INTERFACE\n"); lineno++;
  }
  const char* name = lemp->name ? lemp->name : "Parse";
  if (lemp->arg && lemp->arg[0]) {
    int i = lemonStrlen(lemp->arg);
    while( i>=1 && ISSPACE(lemp->arg[i-1]) ) i--;
    while( i>=1 && (ISALNUM(lemp->arg[i-1]) || lemp->arg[i-1]=='_') ) i--;
    fprintf(out,"#define %sARG_SDECL %s;\n",name,lemp->arg);  lineno++;
    fprintf(out,"#define %sARG_PDECL ,%s\n",name,lemp->arg);  lineno++;
    fprintf(out,"#define %sARG_FETCH %s = yypParser->%s\n",
                 name,lemp->arg,&lemp->arg[i]);  lineno++;
    fprintf(out,"#define %sARG_STORE yypParser->%s = %s\n",
                 name,&lemp->arg[i],&lemp->arg[i]);  lineno++;
  } else {
    fprintf(out,"#define %sARG_SDECL\n",name);  lineno++;
    fprintf(out,"#define %sARG_PDECL\n",name);  lineno++;
    fprintf(out,"#define %sARG_FETCH\n",name); lineno++;
    fprintf(out,"#define %sARG_STORE\n",name); lineno++;
  }
  if (mhflag) {
    fprintf(out,"#endif\n"); lineno++;
  }
  if (lemp->errsym->useCnt) {
    fprintf(out,"#define YYERRORSYMBOL %d\n",lemp->errsym->index); lineno++;
    fprintf(out,"#define YYERRSYMDT yy%d\n",lemp->errsym->dtnum); lineno++;
  }
  if (lemp->has_fallback) {
    fprintf(out,"#define YYFALLBACK 1\n");  lineno++;
  }

  /* Compute the action table, but do not output it yet.  The action
  ** table must be computed before generating the YYNSTATE macro because
  ** we need to know how many states can be eliminated.
  */
  std::vector<struct axset> ax(lemp->nxstate*2);

  for (int i=0; i<lemp->nxstate; i++) {
    State* state = lemp->sorted_states[i];
    ax[i*2].stp = state;
    ax[i*2].isTkn = 1;
    ax[i*2].nAction = state->nTknAct;
    ax[i*2+1].stp = state;
    ax[i*2+1].isTkn = 0;
    ax[i*2+1].nAction = state->nNtAct;
  }
  int mnTknOfst=0, mxTknOfst=0;
  int mnNtOfst=0, mxNtOfst=0;
  /* In an effort to minimize the action table size, use the heuristic
  ** of placing the largest action sets first */
  for (int i=0; i < lemp->nxstate*2; i++) ax[i].iOrder = i;
  std::sort(ax.begin(), ax.end(), [](const axset& a, const axset&b){
      return axset_compare(a, b)<0;});
  struct acttab *pActtab = acttab_alloc();
  for (int i=0; i<lemp->nxstate*2 && ax[i].nAction>0; i++) {
    State* state = ax[i].stp;
    if (ax[i].isTkn) {
      for (Action* ap : state->actions) {
        int action;
        if (ap->sp->index >= lemp->nterminal) continue;
        action = compute_action(lemp, ap);
        if (action < 0) continue;
        acttab_action(pActtab, ap->sp->index, action);
      }
      state->iTknOfst = acttab_insert(pActtab);
      if (state->iTknOfst < mnTknOfst) mnTknOfst = state->iTknOfst;
      if (state->iTknOfst > mxTknOfst) mxTknOfst = state->iTknOfst;
    } else {
      for (Action* ap : state->actions) {
        int action;
        if (ap->sp->index < lemp->nterminal) continue;
        if (ap->sp->index == lemp->nsymbol) continue;
        action = compute_action(lemp, ap);
        if (action < 0) continue;
        acttab_action(pActtab, ap->sp->index, action);
      }
      state->iNtOfst = acttab_insert(pActtab);
      if (state->iNtOfst<mnNtOfst) mnNtOfst = state->iNtOfst;
      if (state->iNtOfst>mxNtOfst) mxNtOfst = state->iNtOfst;
    }
#if 0  /* Uncomment for a trace of how the yy_action[] table fills out */
    {
      for (int jj=0,nn=0; jj<pActtab->nAction; jj++) {
        if (pActtab->aAction[jj].action<0) nn++;
      }
      printf("%4d: State %3d %s n: %2d size: %5d freespace: %d\n",
             i, state->statenum, ax[i].isTkn ? "Token" : "Var  ",
             ax[i].nAction, pActtab->nAction, nn);
    }
#endif
  }

  /* Finish rendering the constants now that the action table has
  ** been computed */
  fprintf(out,"#define YYNSTATE             %d\n",lemp->nxstate);  lineno++;
  fprintf(out,"#define YYNRULE              %d\n",lemp->nrule);  lineno++;
  fprintf(out,"#define YY_MAX_SHIFT         %d\n",lemp->nxstate-1); lineno++;
  fprintf(out,"#define YY_MIN_SHIFTREDUCE   %d\n",nstate); lineno++;
  int i = nstate + lemp->nrule;
  fprintf(out,"#define YY_MAX_SHIFTREDUCE   %d\n", i-1); lineno++;
  fprintf(out,"#define YY_MIN_REDUCE        %d\n", i); lineno++;
  i = nstate + lemp->nrule*2;
  fprintf(out,"#define YY_MAX_REDUCE        %d\n", i-1); lineno++;
  fprintf(out,"#define YY_ERROR_ACTION      %d\n", i); lineno++;
  fprintf(out,"#define YY_ACCEPT_ACTION     %d\n", i+1); lineno++;
  fprintf(out,"#define YY_NO_ACTION         %d\n", i+2); lineno++;
  tplt_xfer(lemp->name, in, out, &lineno);

  /* Now output the action table and its associates:
  **
  **  yy_action[]        A single table containing all actions.
  **  yy_lookahead[]     A table containing the lookahead for each entry in
  **                     yy_action.  Used to detect hash collisions.
  **  yy_shift_ofst[]    For each state, the offset into yy_action for
  **                     shifting terminals.
  **  yy_reduce_ofst[]   For each state, the offset into yy_action for
  **                     shifting non-terminals after a reduce.
  **  yy_default[]       Default action for each state.
  */

  /* Output the yy_action table */
  int n = acttab_size(pActtab);
  lemp->nactiontab = n;
  lemp->tablesize += n*szActionType;
  fprintf(out,"#define YY_ACTTAB_COUNT (%d)\n", n); lineno++;
  fprintf(out,"static const YYACTIONTYPE yy_action[] = {\n"); lineno++;
  for (int i=0, j=0; i<n; i++) {
    int action = acttab_yyaction(pActtab, i);
    if (action<0) action = nstate + lemp->nrule + 2;
    if (j==0) fprintf(out," /* %5d */ ", i);
    fprintf(out, " %4d,", action);
    if (j==9 || i==n-1) {
      fprintf(out, "\n"); lineno++;
      j = 0;
    } else {
      j++;
    }
  }
  fprintf(out, "};\n"); lineno++;

  /* Output the yy_lookahead table */
  lemp->tablesize += n*szCodeType;
  fprintf(out,"static const YYCODETYPE yy_lookahead[] = {\n"); lineno++;
  for (int i=0,j=0; i<n; i++) {
    int la = acttab_yylookahead(pActtab, i);
    if (la<0) la = lemp->nsymbol;
    if (j==0) fprintf(out," /* %5d */ ", i);
    fprintf(out, " %4d,", la);
    if (j==9 || i==n-1) {
      fprintf(out, "\n"); lineno++;
      j = 0;
    } else {
      j++;
    }
  }
  fprintf(out, "};\n"); lineno++;

  /* Output the yy_shift_ofst[] table */
  fprintf(out, "#define YY_SHIFT_USE_DFLT (%d)\n", mnTknOfst-1); lineno++;
  n = lemp->nxstate;
  while( n>0 && lemp->sorted_states[n-1]->iTknOfst==NO_OFFSET ) n--;
  fprintf(out, "#define YY_SHIFT_COUNT (%d)\n", n-1); lineno++;
  fprintf(out, "#define YY_SHIFT_MIN   (%d)\n", mnTknOfst); lineno++;
  fprintf(out, "#define YY_SHIFT_MAX   (%d)\n", mxTknOfst); lineno++;
  int sz;
  fprintf(out, "static const %s yy_shift_ofst[] = {\n", 
          minimum_size_type(mnTknOfst-1, mxTknOfst, &sz)); lineno++;
  lemp->tablesize += n*sz;
  for (int i=0,j=0; i<n; i++) {
    int ofst;
    State* stp = lemp->sorted_states[i];
    ofst = stp->iTknOfst;
    if (ofst==NO_OFFSET) ofst = mnTknOfst - 1;
    if (j==0) fprintf(out," /* %5d */ ", i);
    fprintf(out, " %4d,", ofst);
    if (j==9 || i==n-1) {
      fprintf(out, "\n"); lineno++;
      j = 0;
    } else {
      j++;
    }
  }
  fprintf(out, "};\n"); lineno++;

  /* Output the yy_reduce_ofst[] table */
  fprintf(out, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst-1); lineno++;
  n = lemp->nxstate;
  while( n>0 && lemp->sorted_states[n-1]->iNtOfst==NO_OFFSET ) n--;
  fprintf(out, "#define YY_REDUCE_COUNT (%d)\n", n-1); lineno++;
  fprintf(out, "#define YY_REDUCE_MIN   (%d)\n", mnNtOfst); lineno++;
  fprintf(out, "#define YY_REDUCE_MAX   (%d)\n", mxNtOfst); lineno++;
  fprintf(out, "static const %s yy_reduce_ofst[] = {\n", 
          minimum_size_type(mnNtOfst-1, mxNtOfst, &sz)); lineno++;
  lemp->tablesize += n*sz;
  for (int i=0,j=0; i<n; i++) {
    int ofst;
    State* stp = lemp->sorted_states[i];
    ofst = stp->iNtOfst;
    if (ofst==NO_OFFSET) ofst = mnNtOfst - 1;
    if (j==0) fprintf(out," /* %5d */ ", i);
    fprintf(out, " %4d,", ofst);
    if (j==9 || i==n-1) {
      fprintf(out, "\n"); lineno++;
      j = 0;
    } else {
      j++;
    }
  }
  fprintf(out, "};\n"); lineno++;

  /* Output the default action table */
  fprintf(out, "static const YYACTIONTYPE yy_default[] = {\n"); lineno++;
  n = lemp->nxstate;
  lemp->tablesize += n*szActionType;
  for (int i=0,j=0; i<n; i++) {
    State* stp = lemp->sorted_states[i];
    if (j==0) fprintf(out," /* %5d */ ", i);
    fprintf(out, " %4d,", stp->iDfltReduce+nstate+lemp->nrule);
    if (j==9 || i==n-1) {
      fprintf(out, "\n"); lineno++;
      j = 0;
    } else {
      j++;
    }
  }
  fprintf(out, "};\n"); lineno++;
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate the table of fallback tokens.
  */
  if (lemp->has_fallback) {
    int mx = lemp->nterminal - 1;
    while (mx>0 && lemp->symbols[mx]->fallback==0) { mx--; }
    lemp->tablesize += (mx+1)*szCodeType;
    for (i=0; i<=mx; i++) {
      Symbol *p = lemp->symbols[i];
      if (p->fallback==0) {
        fprintf(out, "    0,  /* %10s => nothing */\n", p->name);
      } else {
        fprintf(out, "  %3d,  /* %10s => %s */\n", p->fallback->index,
          p->name, p->fallback->name);
      }
      lineno++;
    }
  }
  tplt_xfer(lemp->name, in, out, &lineno);

  char line[LINESIZE];
  /* Generate a table containing the symbolic name of every symbol
  */
  for (int i=0; i<lemp->nsymbol; i++) {
    sprintf(line,"\"%s\",",lemp->symbols[i]->name);
    fprintf(out,"  %-15s",line);
    if ((i&3)==3) { fprintf(out,"\n"); lineno++; }
  }
  if ((i&3)!=0) { fprintf(out,"\n"); lineno++; }
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate a table containing a text string that describes every
  ** rule in the rule set of the grammar.  This information is used
  ** when tracing REDUCE actions.
  */
  i = 0;
  for (Rule* rp : lemp->rules) {
    assert( rp->iRule==i );
    fprintf(out," /* %3d */ \"", i++);
    writeRuleText(out, rp);
    fprintf(out,"\",\n"); lineno++;
  }
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate code which executes every time a symbol is popped from
  ** the stack while processing errors or while destroying the parser. 
  ** (In other words, generate the %destructor actions)
  */
  if (lemp->tokendest) {
    int once = 1;
    for (i=0; i<lemp->nsymbol; i++) {
      Symbol *sp = lemp->symbols[i];
      if (sp==0 || sp->type!=TERMINAL) continue;
      if (once) {
        fprintf(out, "      /* TERMINAL Destructor */\n"); lineno++;
        once = 0;
      }
      fprintf(out,"    case %d: /* %s */\n", sp->index, sp->name); lineno++;
    }
    for (i=0; i<lemp->nsymbol && lemp->symbols[i]->type!=TERMINAL; i++);
    if (i<lemp->nsymbol) {
      emit_destructor_code(out,lemp->symbols[i],lemp,&lineno);
      fprintf(out,"      break;\n"); lineno++;
    }
  }
  if (lemp->vardest) {
    Symbol *dflt_sp = 0;
    int once = 1;
    for (i=0; i<lemp->nsymbol; i++) {
      Symbol *sp = lemp->symbols[i];
      if (sp==0 || sp->type==TERMINAL ||
          sp->index<=0 || sp->destructor!=0) continue;
      if (once) {
        fprintf(out, "      /* Default NON-TERMINAL Destructor */\n"); lineno++;
        once = 0;
      }
      fprintf(out,"    case %d: /* %s */\n", sp->index, sp->name); lineno++;
      dflt_sp = sp;
    }
    if (dflt_sp!=0) {
      emit_destructor_code(out,dflt_sp,lemp,&lineno);
    }
    fprintf(out,"      break;\n"); lineno++;
  }
  for (int i=0; i<lemp->nsymbol; i++) {
    Symbol *sp = lemp->symbols[i];
    if (sp==0 || sp->type==TERMINAL || sp->destructor==0 || sp->destructor_emitted) continue;
    fprintf(out,"    case %d: /* %s */\n", sp->index, sp->name); lineno++;
    sp->destructor_emitted = 1;

    /* Combine duplicate destructors into a single case */
    for (int j=i+1; j<lemp->nsymbol; j++) {
      Symbol *sp2 = lemp->symbols[j];
      if (sp2 && sp2->type!=TERMINAL && sp2->destructor
          && sp2->dtnum==sp->dtnum
          && strcmp(sp->destructor,sp2->destructor)==0) {
         fprintf(out,"    case %d: /* %s */\n",
                 sp2->index, sp2->name); lineno++;
         //sp2->destructor = 0; // bugfix: laterly used by translate_code
         sp2->destructor_emitted = 1;
      }
    }

    emit_destructor_code(out,lemp->symbols[i],lemp,&lineno);
    fprintf(out,"      break;\n"); lineno++;
  }
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate code which executes whenever the parser stack overflows */
  tplt_print(out,lemp,lemp->overflow,&lineno);
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate the table of rule information 
  **
  ** Note: This code depends on the fact that rules are number
  ** sequentually beginning with 0.
  */
  for (Rule* rule : lemp->rules) {
    fprintf(out,"  { %d, %d },\n", rule->lhs->index, (int)rule->rhs.size()); lineno++;
  }
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate code which execution during each REDUCE action */
  i = 0;
  for (Rule* rule : lemp->rules) {
    i += translate_code(lemp, rule);
  }
  if (i) {
    fprintf(out,"        YYMINORTYPE yylhsminor;\n"); lineno++;
  }
  /* First output rules other than the default: rule */
  for (int i=0; i < lemp->rules.size(); ++i) {
    Rule* rp = lemp->rules.at(i);
    if (rp->code==0) continue;
    if (rp->code[0]=='\n'
     && rp->code[1]==0
     && rp->codePrefix==0
     && rp->codeSuffix==0
   ) {
      /* No actions, so this will be part of the "default:" rule */
      continue;
    }
    fprintf(out,"      case %d: /* ", rp->iRule);
    writeRuleText(out, rp);
    fprintf(out, " */\n"); lineno++;
    for (int j=i+1; j < lemp->rules.size(); ++j) {
      Rule *rp2 = lemp->rules.at(j);    /* Other rules with the same action */
      if (rp2->code==rp->code && rp2->codePrefix==rp->codePrefix
             && rp2->codeSuffix==rp->codeSuffix) {
        fprintf(out,"      case %d: /* ", rp2->iRule);
        writeRuleText(out, rp2);
        fprintf(out," */ yytestcase(yyruleno==%d);\n", rp2->iRule); lineno++;
        rp2->code = 0;
      }
    }
    emit_code(out,rp,lemp,&lineno);
    fprintf(out,"        break;\n"); lineno++;
    rp->code = 0;
  }
  /* Finally, output the default: rule.  We choose as the default: all
  ** empty actions. */
  fprintf(out,"      default:\n"); lineno++;
  for (Rule* rp : lemp->rules) {
    if (rp->code==0) continue;
    assert( rp->code[0]=='\n' && rp->code[1]==0 );
    assert( rp->codePrefix==0 );
    assert( rp->codeSuffix==0 );
    fprintf(out,"      /* (%d) ", rp->iRule);
    writeRuleText(out, rp);
    fprintf(out, " */ yytestcase(yyruleno==%d);\n", rp->iRule); lineno++;
  }
  fprintf(out,"        break;\n"); lineno++;
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate code which executes if a parse fails */
  tplt_print(out,lemp,lemp->failure,&lineno);
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate code which executes when a syntax error occurs */
  tplt_print(out,lemp,lemp->error,&lineno);
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate code which executes when the parser accepts its input */
  tplt_print(out,lemp,lemp->accept,&lineno);
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Append any addition code the user desires */
  tplt_print(out,lemp,lemp->extracode,&lineno);

  fclose(in);
  fclose(out);
  return;
}

/* Generate a header file for the parser */
void ReportHeader(Lemon *lemp)
{
  FILE *out, *in;
  const char *prefix;
  char line[LINESIZE];
  char pattern[LINESIZE];
  int i;

  if (lemp->tokenprefix) prefix = lemp->tokenprefix;
  else                    prefix = "";
  in = file_open(lemp,".h","rb");
  if (in) {
    int nextChar;
    for (i=1; i<lemp->nterminal && fgets(line,LINESIZE,in); i++) {
      sprintf(pattern,"#define %s%-30s %3d\n",
                    prefix,lemp->symbols[i]->name,i);
      if (strcmp(line,pattern)) break;
    }
    nextChar = fgetc(in);
    fclose(in);
    if (i==lemp->nterminal && nextChar==EOF) {
      /* No change in the file.  Don't rewrite it. */
      return;
    }
  }
  out = file_open(lemp,".h","wb");
  if (out) {
    for (i=1; i<lemp->nterminal; i++) {
      fprintf(out,"#define %s%-30s %3d\n",prefix,lemp->symbols[i]->name,i);
    }
    fclose(out);  
  }
  return;
}
#if !defined(NDEBUG)
/* explicit instanciation, for debug */
template class std::map<Rule*, int>;
#endif
/* Reduce the size of the action tables, if possible, by making use
** of defaults.
**
** In this version, we take the most frequent REDUCE action and make
** it the default.  Except, there is no default if the wildcard token
** is a possible look-ahead.
*/
void CompressTables(Lemon *lemp)
{
  for (State* state : lemp->sorted_states) {
    int usesWildcard = 0;
    std::map<Rule*, int> frequency;
    for (Action* ap : state->actions) {
      if (ap->type == SHIFT && ap->sp == lemp->wildcard) {
        usesWildcard = 1;
      }
      if (ap->type == REDUCE && !ap->x.rp->lhsStart)
        ++frequency[ap->x.rp];
    }

    Rule* rbest = 0;
    int nbest = 0;
    if (!frequency.empty()) {
      using elem = decltype(frequency)::value_type;
      auto x = std::max_element(frequency.begin(), frequency.end(),
                 [](const elem& a, const elem& b) {return a.second < b.second;});
      rbest = x->first;
      nbest = x->second;
    }
 
    /* Do not make a default if the number of rules to default
    ** is not at least 1 or if the wildcard token is a possible
    ** lookahead.
    */
    if (nbest<1 || usesWildcard) continue;


    /* Combine matching REDUCE actions into a single default */
    auto first = std::find_if(state->actions.begin(), state->actions.end(),
                           [rbest](Action*& a){return a->type==REDUCE && a->x.rp==rbest;});
    assert(first != state->actions.end());
    (*first)->sp = Symbol_new("{default}");
    std::for_each (std::next(first), state->actions.end(), [rbest](Action*& ap){
        if (ap->type == REDUCE && ap->x.rp == rbest)
          ap->type = NOT_USED;
      });

    /* Check if this is an autoReduce state */
    Action_sort(state->actions); // sort {default} to last
    auto it = std::find_if(state->actions.begin(), state->actions.end(), [rbest](Action*& a){
         return (a->type == SHIFT) || (a->type == REDUCE && a->x.rp != rbest);
      });
    if (it == state->actions.end()) { // state only have {default} action is autoReduce
      state->autoReduce = 1;
      state->pDfltReduce = rbest;
    }
  }

  /* Make a second pass over all states and actions.  Convert
  ** every action that is a SHIFT to an autoReduce state into
  ** a SHIFTREDUCE action.
  */
  for (State* state : lemp->sorted_states) {
    for (Action* ap : state->actions) {
      if (ap->type != SHIFT) continue;
      State* pNextState = ap->x.stp;
      if (pNextState->autoReduce && pNextState->pDfltReduce!=0) {
        ap->type = SHIFTREDUCE;
        ap->x.rp = pNextState->pDfltReduce;
      }
    }
  }
}


/*
** Compare two states for sorting purposes.  The smaller state is the
** one with the most non-terminal actions.  If they have the same number
** of non-terminal actions, then the smaller is the one with the most
** token actions.
*/
static int stateResortCompare(const void *a, const void *b){
  const State *pA = *(const State**)a;
  const State *pB = *(const State**)b;
  int n;

  n = pB->nNtAct - pA->nNtAct;
  if (n==0) {
    n = pB->nTknAct - pA->nTknAct;
    if (n==0) {
      n = pB->statenum - pA->statenum;
    }
  }
  assert( n!=0 );
  return n;
}


/*
** Renumber and resort states so that states with fewer choices
** occur at the end.  Except, keep state 0 as the first state.
*/
void ResortStates(Lemon *lemp)
{
  int nstate = lemp->sorted_states.size();

  for (State* state : lemp->sorted_states) {
    state->nTknAct = state->nNtAct = 0;
    state->iDfltReduce = lemp->nrule;  /* Init dflt action to "syntax error" */
    state->iTknOfst = NO_OFFSET;
    state->iNtOfst = NO_OFFSET;
    for (Action* act : state->actions) {
      int iAction = compute_action(lemp, act);
      if (iAction >= 0) {
        if (act->sp->index < lemp->nterminal) {
          state->nTknAct++;
        } else if (act->sp->index < lemp->nsymbol) {
          state->nNtAct++;
        } else {
          assert(state->autoReduce==0 || state->pDfltReduce==act->x.rp);
          state->iDfltReduce = iAction - nstate - lemp->nrule;
        }
      }
    }
  }
  qsort(&lemp->sorted_states[1], nstate-1, sizeof(lemp->sorted_states[0]),
        stateResortCompare);
  int i = 0;
  for (State* state : lemp->sorted_states) {
    state->statenum = i++;
  }
  lemp->nxstate = nstate;
  while (lemp->nxstate>1 && lemp->sorted_states[lemp->nxstate-1]->autoReduce) {
    lemp->nxstate--;
  }
}

